//Cracking coding interview, 10.8
//4:03PM--4:23PM--4:39PM(bug free)

#include<iostream>
#include<cstdlib>
using namespace std;


struct Node {
	Node(): l(NULL), r(NULL), numlchilds(0) {}
	int key;
	Node *l, *r;

	int numlchilds;
};

Node *root=NULL;
void TreeIns(Node **root, Node *nd) {
	if(!*root) {
		*root=nd;
	} else {
		if((*root)->key>=nd->key) {
			TreeIns(&(*root)->l, nd);
			(*root)->numlchilds++;
		} else {
			TreeIns(&(*root)->r, nd);
		}
	}
}

int TreeSearch(Node *root, int key) {
	if(!root) return 0;
	if(root->key>key) {
		return TreeSearch(root->l, key);
	} else if(root->key<key) {
		return TreeSearch(root->r, key)+1+root->numlchilds;
	} else {
		return root->numlchilds;
	}
}

void track(int x) {
	Node *n=new Node;
	n->key=x;
	TreeIns(&root, n);
}

int getRankOfNumber(int x) {
	return TreeSearch(root, x);
}

int main(int argc, char *argv[]) {
	int input[]={5, 1, 4, 4, 5, 9, 7, 13, 3};
	for(int i=0; i<9; i++) {
		track(input[i]);
	}

	int r1=getRankOfNumber(1);
	int r2=getRankOfNumber(3);
	int r3=getRankOfNumber(4);

	return 0;
}